337C - Quiz - CodeForces Solution

#include <bits/stdc++.h>

using namespace std;

#define fast_io ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)

typedef long long ll;

ll mod(ll a, ll m) {                          // returns a (mod m)
  return ((a%m) + m) % m;                        // ensure positive answer
}

ll modPow(ll b, ll p, ll m) {                // assume 0 <= b < m
  if (p == 0) return 1;
  ll ans = modPow(b, p/2, m);                   // this is O(log p)
  ans = mod(ans*ans, m);                         // double it first
  if (p&1) ans = mod(ans*b, m);                  // *b if p is odd
  return ans;                                    // ans always in [0..m-1]
}

#define mo int(1000000009)

int main(){
    ll n,m,k;
    cin >> n >> m >> k;
    if(n >= 2*m){
        cout << m ;
    }else{
        ll sol = k;
        ll x = max(0ll, m - (n - n % k) / k * (k-1) - n % k);
        ll dble = modPow(2,x + 1,mo);
        sol = (sol * (dble-2) )%mo;
        sol += m - x*k;
        cout << mod(sol, mo);
    }
}